/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include<iostream>
#include<string>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	maxPid = -1;
	treeHeight = 0;
}

/*
Call this when you are initializing your B+Tree for the first time.
*/
RC BTreeIndex::initializeIndex(const string& indexname)
{
	pf.open(indexname,'w');

	PageId initRootId = -1;
	PageId initMaxPid = -1;
	int initTreeHeight = 0;
    memset(buffer, 0, PageFile::PAGE_SIZE);
	memcpy(&buffer[0], &initRootId, sizeof(PageId));
	memcpy(&buffer[sizeof(PageId)], &initMaxPid, sizeof(PageId));
	memcpy(&buffer[sizeof(PageId)+sizeof(PageId)], &initTreeHeight, sizeof(int));

	pf.write(0,&buffer); //write PageId 0 from buffer

	//pf.close();

	return 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC openres = pf.open(indexname,mode);
	if (openres < 0)
		return openres;
	if (pf.endPid() <= 0) {
		initializeIndex(indexname);
	}

	//read in height of tree, maxPid, rootPid from Page 0(where they are stored)
	RC pfreadres = pf.read(0,&buffer); //read PageId 0 into buffer
	if (pfreadres < 0)
		return pfreadres;
	memcpy(&rootPid,&buffer[0],sizeof(PageId));
	memcpy(&maxPid,&buffer[sizeof(PageId)],sizeof(PageId));
	memcpy(&treeHeight,&buffer[sizeof(PageId)+sizeof(PageId)],sizeof(int));

	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	//write height of tree, maxPid, rootPid to disk
	memcpy(&buffer[0], &rootPid, sizeof(PageId));
	memcpy(&buffer[sizeof(PageId)], &maxPid, sizeof(PageId));
	memcpy(&buffer[sizeof(PageId)+sizeof(PageId)], &treeHeight, sizeof(int));
	RC pfwriteres = pf.write(0,&buffer); //write PageId 0 from buffer
	if (pfwriteres < 0)
		return pfwriteres;

	RC closeres = pf.close();
	if (closeres < 0)
		return closeres;

	return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	//cout << "rid: " << rid.pid << ", sid: " << rid.sid << endl;
	int res = -1;

	//if no Pages in PageFile, create new page and root node
	if (maxPid == -1) {
		BTLeafNode* btln = new BTLeafNode();
		rootPid = 1;
		maxPid = 1;
		treeHeight = 1;
		btln->insert(key,rid);
		btln->setNextNodePtr(-1);
		btln->write(1,pf);
	}
	else {
		res = insertRecursive(key,rid,rootPid,1);
		//cout << "result of insert: " << res << endl;

		//Create new root node, if needed (don't forget to increment tree height!)
		if (res >= 0) {
			BTNonLeafNode* newRoot = new BTNonLeafNode();
			newRoot->initializeRoot(rootPid,res,maxPid);

			newRoot->write(maxPid+1,pf);
			rootPid = maxPid+1;
			maxPid++;
			treeHeight++;
		}
		//cout << "root pid: " << rootPid << endl;
		//cout << "max pid: " << maxPid << endl;
	}
    return 0;
}

int BTreeIndex::insertRecursive(int key, const RecordId& rid, PageId& pid, int recurseLevel)
{
	//cout << "Recurse Level: " << recurseLevel << endl;
	int result = -1;

	//Base case: We're at a leaf node
	if (recurseLevel >= treeHeight)
	{
		BTLeafNode* btln = new BTLeafNode();

			RC readres = btln->read(pid,pf);
			//cout << "readres: " << readres << endl;
			int pushToParentKey = -1;

			int maxLeafKeyCount = (PageFile::PAGE_SIZE - sizeof(PageId))/(sizeof(RecordId)+sizeof(int));

			//leaf node is not full
			if (btln->getKeyCount() < maxLeafKeyCount) {
				btln->insert(key,rid);
			}
			else { //leaf node is full
				PageId nextSiblingPtr = btln->getNextNodePtr();
				//cout << "next sibling ptr: " << nextSiblingPtr << endl;
				BTLeafNode* siblingbtln = new BTLeafNode();
				btln->insertAndSplit(key,rid,*siblingbtln,pushToParentKey);
				//cout << "max pid: " << maxPid << endl;
				btln->setNextNodePtr(maxPid + 1);
				siblingbtln->setNextNodePtr(nextSiblingPtr);

				//cout << "orig next ptr: " << btln->getNextNodePtr() << endl;
				//cout << "sibling next ptr: " << siblingbtln->getNextNodePtr() << endl;
				RC sibwriteres = siblingbtln->write(maxPid + 1,pf);
				//cout << "sibwriteres: " << sibwriteres << endl;
				maxPid++;
				result = pushToParentKey;
			}
			RC writeres = btln->write(pid,pf);
			//cout << "writeres: " << writeres << endl;

			return result;
	}
	else { //We're at a non-leaf node
		BTNonLeafNode* btnln = new BTNonLeafNode();
		RC nlnreadres = btnln->read(pid,pf);
		//cout << "nlnreadres: " << nlnreadres << endl;
		PageId nextPid;
		int keyToInsertHere;
		int maxNonLeafKeyCount = (PageFile::PAGE_SIZE - sizeof(PageId))/(sizeof(PageId)+sizeof(int));

		//locate which child ptr to follow
		btnln->locateChildPtr(key,nextPid);

		//recursively call insertAtNode with that child ptr and recurseLevel+1
		keyToInsertHere = insertRecursive(key,rid,nextPid,recurseLevel+1);
		//cout << "Key To Insert Here: " << keyToInsertHere << endl;

		//we need to insert key into this node
		if (keyToInsertHere >= 0) {
			//this node is not full, insert without split
			if (btnln->getKeyCount() < maxNonLeafKeyCount) {
				btnln->insert(keyToInsertHere,maxPid); //maxPid is Pid of node in level below that was just created. based on assumptions of how insert on B+Tree works
			}
			else { //this node is full, insert and split
				BTNonLeafNode* siblingbtnln = new BTNonLeafNode();
				int pushToParentKey = -1;
				btnln->insertAndSplit(keyToInsertHere,maxPid,*siblingbtnln,pushToParentKey);
				siblingbtnln->write(maxPid+1,pf);
				maxPid++;
				result = pushToParentKey;
			}
		}
		btnln->write(pid,pf);
		return result;
	}
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	RC locateRecursiveRes = locateRecursive(searchKey,cursor,rootPid,1);
    return locateRecursiveRes;
}

RC BTreeIndex::locateRecursive(int searchKey, IndexCursor& cursor, PageId pid, int recurseLevel)
{

	//Base Case: We're at a leaf node
	if (recurseLevel == treeHeight) {
		BTLeafNode* btln = new BTLeafNode();
		btln->read(pid,pf);
		int slotId = -1;

		//locate correct slot ID
		RC leafres = btln->locate(searchKey,slotId);
		if (leafres < 0)
			return leafres;

		//set the fields for resulting IndexCursor
		cursor.pid = pid;
		cursor.eid = slotId;

		return 0;
	}
	else {
		BTNonLeafNode* btnln = new BTNonLeafNode();
		btnln->read(pid,pf);
		PageId nextPid;

		//locate child ptr to follow
		RC nonleafres = btnln->locateChildPtr(searchKey,nextPid);
		if (nonleafres < 0)
			return nonleafres;

		RC recurseres = locateRecursive(searchKey,cursor,nextPid,recurseLevel+1);
		return recurseres;
	}
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    BTLeafNode* btln = new BTLeafNode();
	RC readres = btln->read(cursor.pid,pf);
	if (readres < 0)
		return readres;

	//set key, rid for output
	RC readentryres = btln->readEntry(cursor.eid,key,rid);
	if(readentryres < 0)
		return readentryres;

	//set cursor for output
	if (btln->getNextNodePtr() == -1 && cursor.eid == btln->getKeyCount()) {
		cursor.eid = -1;
		cursor.pid = -1;
		return 0;
	}
	if (cursor.eid < btln->getKeyCount()) {
		cursor.eid++;
	}
	else {
		cursor.pid = btln->getNextNodePtr();
		cursor.eid = 0;
	}

	return 0;
}

/*
int main()
{
	BTreeIndex* bti = new BTreeIndex();
	bti->open("testindex.idx",'r');

	RecordId testrid;
	testrid.pid = 3;
	testrid.sid = 5;
	for (int i = 3001; i < 4000; i++) {
		bti->insert(i,testrid);
	}
	IndexCursor rescursor;
	bti->locate(1000,rescursor);
	cout << "cursor pid: " << rescursor.pid << endl;
	cout << "cursor eid: " << rescursor.eid << endl;

	bti->close();
}
*/

